package com.yangzhe.algorithm.c036;

import java.util.HashMap;
import java.util.Map;

// 利用先序与中序遍历序列构造二叉树
// 测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
public class Code05_PreorderSerializeAndDeserialize_LeetCode {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int v) {
            val = v;
        }
    }

    /**
     * 思路：
     * 1. 先序：中左右，中序：左中右。且遍历是有规律的即：左树，右树的节点在数组中都是连续的index
     * 2. 先序第一个是头，每个部分开始的第一个都是头，接下来是左树，右树
     * 3. 在 中序队列 中找到头的位置k，左边是左树，右边是右树
     * 4. 左树：计算中序队列 左树的个数k，从先序队列中往后数k个，则先序队列的第k+1个节点就是左树的头
     * 5. 右树：同左树
     *
     * @param pre
     * @param in
     * @return
     */
    public static TreeNode buildTree(int[] pre, int[] in) {
        if (pre == null || pre.length == 0) {
            return null;
        }
        // key=TreeNode.val  value=在中序数组中的index
        // 用于快速定位，否则每次查找都要全量遍历，HashMap get是O(1)的复杂度
        Map<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            inMap.put(in[i], i);
        }

        return build(pre, 0, pre.length - 1, in, 0, in.length - 1, inMap);
    }

    public static TreeNode build(int[] pre, int preL, int preR, int[] in, int inL, int inR, Map<Integer, Integer> inMap) {
        // base case: 当前范围没节点
        if (preL > preR) {
            return null;
        }
        // 先序每个部分开始的第一个都是头
        TreeNode head = new TreeNode(pre[preL]);

        int k = inMap.get(head.val);
        // 排除掉k位置，左树的数量
        int leftTreeCount = k - inL;

        // 找到先序和中序的左部分，开始递归
        head.left = build(pre, preL + 1, preL + leftTreeCount, in, inL, k - 1, inMap);
        // 找到先序和中序的右部分，开始递归
        head.right = build(pre, preL + leftTreeCount + 1, preR, in, k + 1, inR, inMap);

        return head;
    }

}
